package cn.tedu.mall.search.test;

public class hebingyouxuliebiao {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.next.next.next.next.next.next = new Node(7);

        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(5);
        head1.next.next.next = new Node(6);
        head1.next.next.next.next = new Node(8);
        head1.next.next.next.next.next = new Node(10);

        Node head3 = hebing(head, head1);
        Node n = head3;
        while (n != null) {
            System.out.println(n.value);
            n = n.next;
        }
    }

    private static Node hebing(Node n1, Node n2) {
        Node tmp = new Node(0);
        Node n3 = tmp;
        while (n1 != null && n2 != null) {
            if (n1.value < n2.value) {
                n3.next = new Node(n1.value);
                n3 = n3.next;
                n1 = n1.next;
            } else {
                n3.next = new Node(n2.value);
                n3 = n3.next;
                n2 = n2.next;
            }
        }
        if (n1 != null) {
            n3.next = n1;
        } else {
            n3.next = n2;
        }
        return tmp.next;
    }

    static class Node {
        int value;
        Node prev;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }
}
